1. Field of the Invention
The present invention relates to schedulers and techniques for communicating signals through switches. More specifically, the present invention relates to a technique for determining a schedule for a switch.
2. Related Art
Large switches with hundreds of input and output ports and terabit-per-second throughput use schedulers (which are sometimes referred to as ‘arbiters’) to match input ports with output ports to forward data at high rates. In switches where the data is partitioned into fixed-size data packets (or data cells), one of the main challenges in designing a scheduler is to provide a maximal matching between the input ports and the output ports for every data cell transmission time (which is sometimes referred to as a slot).
However, because data-cell sizes tend to remain constant, as link data rates increase the corresponding slot size decreases. Consequently, the scheduler may have less time to determine a maximal matching for data cells arriving at the input ports. Moreover, determining a schedule for a switch with a large number of input ports and output ports is further complicated because the computation time increases significantly as the total number of ports increases. In many existing switches, these problems are addressed using complicated schedulers that require a significant amount of time to determine the maximal matching between input ports and output ports.
Additionally, when executing applications that require tight coupling between computation nodes, low latency is important. Typically, communication networks are engineered such that switches operate under light load most of the time to avoid forwarding delays caused by high loads. Consequently, the latency of a switch operating under a light load can be an important design parameter. Unfortunately, it can be difficult to achieve a low latency under a light load using a complicated scheduler.
Hence, what is needed are schedulers and techniques for determining a schedule for a switch without the problems described above.